#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, string> edges;
        unordered_map<char, int> word;
        queue<char> q;
        vector<int> in(26, -1);
        for (int i = 0; i < words.size(); i++)
            for (int j = i + 1; j < words.size(); j++)
            {
                int a;
                for (a = 0; a < words[i].size() && a < words[j].size(); a++)
                    if (words[i][a] != words[j][a])
                    {
                        edges[words[i][a]].push_back(words[j][a]);
                        if (in[words[i][a] - 'a'] == -1) in[words[i][a] - 'a']++;
                        if (in[words[j][a] - 'a'] == -1) in[words[j][a] - 'a'] = 1;
                        else in[words[j][a] - 'a']++;
                        break;
                    }
                if (a == words[j].size() && a < words[i].size()) return "";
            }
        for (int i = 0; i < words.size(); i++)
            for (auto& st : words[i]) if (word.count(st) == 0) word[st]++;
        for (int i = 0; i < 26; i++) if (in[i] == 0) q.push(i + 'a');
        string ret;
        while (q.size())
        {
            char ch = q.front();
            q.pop();
            if (in[ch - 'a'] > 0) return "";
            ret.push_back(ch);
            word[ch]--;
            for (char c : edges[ch]) if (--in[c - 'a'] == 0) q.push(c);
        }
        for (int i = 0; i < 26; i++) if (in[i] > 0) return "";
        for (auto [x, y] : word) if (y == 1) ret.push_back(x);
        return ret;
    }
};